POJ 1981 Circle and Points(极限情况、极角扫描)

题意:

$N\le 300个点,问1个单位圆最多能包住几个点,在边界上也可以$
$保证最多只有2个点在圆上$

分析:

$极限情况辣,肯定是有2个点在圆上的,暴力枚举2个点是n^2$
$然后几何姿势找到圆心,转转向量啥的,之后再看有多个在圆内,O(n^3)$
$蓝儿其实可以不这么想,考虑能包住每个点的圆是啥样的$
$也就是说每个点作为圆心的单位圆,对于任意2个点能共同包住的部分显然是相交的那部分$
$这是一个圆弧,我们可以用极角来表示这些圆弧,进入角度和出去角度$
$事实上对于每个点,和其他点的形成的圆交的圆弧,求一个并,那么最大的并就是答案了$
$至于求并,极角排序以后,+1-1极角扫描合并就可以了$
$时间复杂度O(n^2logn)$

$代码O(n^3):$

//
//  Created by TaoSama on 2016-08-23
//  Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 300 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
const double EPS = 1e-8;

int sgn(double x) {
    return x < -EPS ? -1 : x > EPS;
}

int n;
struct Point {
    double x, y;
    Point() {}
    Point(double x, double y): x(x), y(y) {}
    inline void read() {
        scanf("%lf%lf", &x, &y);
    }
    inline Point operator+(const Point& p) const {
        return Point(x + p.x, y + p.y);
    }
    inline Point operator-(const Point& p) const {
        return Point(x - p.x, y - p.y);
    }
    inline Point operator*(const double& k) const {
        return Point(k * x, k * y);
    }
    inline double operator*(const Point& p) const {
        return x * p.x + y * p.y;
    }
    inline double operator^(const Point& p) const {
        return x * p.y - y * p.x;
    }
    inline Point rotate(double rad) {
        return Point(x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad));
    }
    inline double length() {
        return sqrt(x * x + y * y);
    }
    inline void norm() {
        double l = length();
        x /= l, y /= l;
    }
    void see() {
        printf("%.4f %.4f\n", x, y);
    }
} ps[N];

typedef Point Vector;

int main() {
#ifdef LOCAL
    freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
//  freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
//    ios_base::sync_with_stdio(0);

    while(scanf("%d", &n) == 1 && n) {
        for(int i = 1; i <= n; ++i) ps[i].read();

        int ans = 1;
        for(int i = 1; i <= n; ++i) {
            for(int j = i + 1; j <= n; ++j) {
                if(i == j) continue;

                Vector AB = ps[j] - ps[i]; //B-A=AB
                double c = AB.length();
                if(sgn(c - 2) > 0) continue;

                double cosTheta = (c * c + 1 - 1) / (2 * c);
                double theta = acos(cosTheta);
                Vector AO = AB.rotate(theta); AO.norm();
                Point O = ps[i] + AO;

                int cnt = 0;
                for(int k = 1; k <= n; ++k)
                    if(sgn((ps[k] - O).length() - 1) <= 0) ++cnt;
                ans = max(ans, cnt);
            }
        }
        printf("%d\n", ans);
    }

    return 0;
}

$O(n^2logn):$

//
//  Created by TaoSama on 2016-08-23
//  Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 300 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
const double EPS = 1e-8;

int sgn(double x) {
    return x < -EPS ? -1 : x > EPS;
}

int n;
struct Point {
    double x, y;
    Point() {}
    Point(double x, double y): x(x), y(y) {}
    inline void read() {
        scanf("%lf%lf", &x, &y);
    }
    inline Point operator+(const Point& p) const {
        return Point(x + p.x, y + p.y);
    }
    inline Point operator-(const Point& p) const {
        return Point(x - p.x, y - p.y);
    }
    inline Point operator*(const double& k) const {
        return Point(k * x, k * y);
    }
    inline double operator*(const Point& p) const {
        return x * p.x + y * p.y;
    }
    inline double operator^(const Point& p) const {
        return x * p.y - y * p.x;
    }
    inline Point rotate(double rad) {
        return Point(x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad));
    }
    inline double length() {
        return sqrt(x * x + y * y);
    }
    inline double angle() {
        return atan2(y, x);
    }
    inline void norm() {
        double l = length();
        x /= l, y /= l;
    }
    void see() {
        printf("%.4f %.4f\n", x, y);
    }
} ps[N];

typedef Point Vector;
pair<double, int> angles[N];

int main() {
#ifdef LOCAL
    freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
//  freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
//    ios_base::sync_with_stdio(0);

    while(scanf("%d", &n) == 1 && n) {
        for(int i = 1; i <= n; ++i) ps[i].read();

        int ans = 1;
        for(int i = 1; i <= n; ++i) {
            int m = 0;
            for(int j = 1; j <= n; ++j) {
                if(i == j) continue;
                Vector AB = ps[j] - ps[i];
                double c = AB.length();
                if(sgn(c - 2) > 0) continue;
                double angle = AB.angle();
                double delta = acos(c / 2);
                angles[m++] = make_pair(angle - delta, 1);
                angles[m++] = make_pair(angle + delta, -1);
            }
            sort(angles, angles + m);

            int cnt = 1;
            for(int j = 0; j < m; ++j) {
                cnt += angles[j].second;
                ans = max(ans, cnt);
            }
        }
        printf("%d\n", ans);
    }

    return 0;
}